package dataStructure;

public class MyHashMap<K, V> {

    private Node<K, V>[] table;

    private int size;

    final double loadFactor = 0.75;

    static class Node<K, V> {

        int hash;

        K key;

        V value;

        Node<K, V> next;

        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

    }

    public void put(K key, V value) {
        // 判断数组是否为空，为空则进行初始化
        if (table == null || table.length == 0) {
            table = new Node[16];
        }
        // 根据key的hashcode值计算出hash值
        int hash = hash(key);
        // 通过hash & len -1 获取元素存储下标
        int index = hash & (table.length - 1);
        // 如果当前位置不存在元素则直接插入
        if (table[index] == null) {
            table[index] = new Node<>(hash, key, value, null);
        } else {
            // 如果当前位置存在元素则与元素比较，相等则覆盖，不相等则插入到链表尾部
            Node<K, V> dummy = new Node<>(0, null, null, table[index]);
            Node<K, V> cur = dummy;
            while (true) {
                if (cur.next != null && cur.next.hash == hash && cur.next.key.equals(key)) {
                    cur.next = new Node<>(hash, key, value, cur.next.next);
                    break;
                }
                if (cur.next == null) {
                    cur.next = new Node<>(hash, key, value, null);
                    break;
                }
                cur = cur.next;
            }
            table[index] = dummy.next;
        }
        // 判断是否需要扩容
        if (++size >= loadFactor * table.length) {
            resize();
        }
    }

    public V get(K key) {
        if (table == null) {
            return null;
        }
        int hash = hash(key);
        int index = hash & (table.length - 1);
        Node<K, V> node = table[index];
        if (node == null) {
            return null;
        }
        while (node != null) {
            if (node.hash == hash && node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    public int hash(K key) {
        return key == null ? 0 : key.hashCode() ^ key.hashCode() >>> 16;
    }

    public void resize() {
        int oldCapacity = table.length;
        // 创建两倍大小的新数组
        Node<K, V>[] newTable = new Node[oldCapacity * 2];
        Node<K, V>[] oldTable = table.clone();
        table = newTable;
        for (Node<K, V> cur : oldTable) {
            // 重新hash所有元素
            while (cur != null) {
                put(cur.key, cur.value);
                cur = cur.next;
            }
        }
    }


}
